package srcUSElectoral;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Computes the number of ways in which the electoral votes of various US States
 * can sum upto 269 which would result in a tie in the election.
 *
 * @author Abhishek Prateek (abhip)
 */
public class USElectoralSubsetSumCalculator
{
    /**
     * Sum value to which subset of the numbers should add upto
     * For US electoral problem, the number of votes should sum upto 269 for a tie
     */
    public static final int SumValue = 269;

    /**
     * The Main method
     * @param args
     */
    public static void main(String[] args)
    {
        USElectoralSubsetSumCalculator subsetSumCalculator = new USElectoralSubsetSumCalculator();

        // First row and first column of subsetSum matrix are extra to act as base cases,
        // hence we need one extra row and column
        int numMatrixRows = subsetSumCalculator.GetNumberOfStates() + 1;
        int numMatrixColumns = SumValue + 1;

        long subsetSumMatrix[][] = subsetSumCalculator.GetSubSetSumMatrix(numMatrixRows, numMatrixColumns);

        // subsetSumMatrix[51][269] would contain number of subsets of the 51 States, whose electoral votes sum upto 269 for a tie.
        System.out.println("Number of subsets summing to " + SumValue + " = " + subsetSumMatrix[numMatrixRows - 1][numMatrixColumns - 1]);

        // List<List<String>> solutions = subsetSumCalculator.GetSolutionSet(subsetSumMatrix, numMatrixRows - 1, numMatrixColumns - 1);
        // subsetSumCalculator.PrintSolutions(solutions);
    }

    /**
     * Map of States and their corresponding Electoral Votes
     */
    HashMap<String, Integer> electoralVotesMap;

    /**
     * List of the States
     */
    List<String> states;

    /**
     * Constructor
     */
    public USElectoralSubsetSumCalculator()
    {
        InitializeElectoralVotesMap();
        InitializeStatesList();
    }

    /**
     * @return Number of States
     */
    public int GetNumberOfStates()
    {
        return this.states.size();
    }

    /**
     * Recursively generates the list of subsets which belong to the solution from subsetSumMatrix.
     * Calls itself to get solutions without including ith state.
     * Calls itself to get solutions including ith state, appends ith state to each of those solutions.
     * Returns union of the above two.
     * @param subsetSumMatrix
     * @param rowId
     * @param columnId
     * @return List of subsets which add upto the given SumValue
     */
    /*
    private List<List<String>> GetSolutionSet(
            long[][] subsetSumMatrix,
            int rowId,
            int columnId)
    {
        List<List<String>> solutions = null;

        if (columnId == 0)
        {
            solutions = new ArrayList<List<String>>();
            solutions.add(new ArrayList<String>());
            return solutions;
        }

        if (rowId == 0)
        {
            // no solution exists
            return null;
        }

        int number = this.electoralVotesMap.get(this.states.get(rowId - 1));

        List<List<String>> solutionsWithoutNumber = GetSolutionSet(subsetSumMatrix, rowId - 1 , columnId);

        if (solutionsWithoutNumber != null)
        {
            if (solutions == null)
            {
                solutions = new ArrayList<List<String>>();
            }

            for (List<String> solution : solutionsWithoutNumber)
            {
                solutions.add(solution);
            }
        }

        if (columnId >= number)
        {
            List<List<String>> solutionsWithNumber = GetSolutionSet(subsetSumMatrix, rowId - 1, columnId - number);

            if (solutionsWithNumber != null)
            {
                if (solutions == null)
                {
                    solutions = new ArrayList<List<String>>();
                }

                for (List<String> solution : solutionsWithNumber)
                {
                    solution.add(this.states.get(rowId - 1));
                    solutions.add(solution);
                }
            }
        }

        return solutions;
    }
    */

    /**
     * Computes subset sum matrix M
     * M[i][j] contains number of subsets whose sum is exactly j, considering the elements from 1 to i
     * @param numMatrixRows
     * @param numMatrixColumns
     * @return M
     */
    private long[][] GetSubSetSumMatrix(int numMatrixRows, int numMatrixColumns)
    {
        long M[][] = new long [numMatrixRows][numMatrixColumns];

        // Base case1:
        // Initialize M[0][j] to 0
        for (int j = 0; j < numMatrixColumns; ++j)
        {
            M[0][j] = 0;
        }

        // Base case2:
        // Initialize M[i][0] to 1
        // Because if you have zero or more numbers to choose, you can pick none to get a sum of 0.
        // Hence, there is 1 way of getting sum 0.
        for (int i = 0; i < numMatrixRows; ++i)
        {
            M[i][0] = 1;
        }

        // Fill up the matrix M, row by row
        for (int i = 1; i < numMatrixRows; ++i)
        {
            int iThNumber = this.electoralVotesMap.get(this.states.get(i-1));

            for (int j = 1; j < numMatrixColumns; ++j)
            {
                long numWaysExcludingIthNumber = M[i-1][j];
                long numWaysIncludingIthNumber = (j - iThNumber) < 0 ? 0 : M[i-1][j - iThNumber];

                M[i][j] = numWaysExcludingIthNumber + numWaysIncludingIthNumber;
            }
        }

        return M;
    }

    /**
     * Initializes the map of States and their corresponding Electoral Votes
     */
    private void InitializeElectoralVotesMap()
    {
        this.electoralVotesMap = new HashMap<String, Integer>();

        this.electoralVotesMap.put("Alabama", 9);
        this.electoralVotesMap.put("Alaska", 3);
        this.electoralVotesMap.put("Arizona", 11);
        this.electoralVotesMap.put("Arkansas", 6);
        this.electoralVotesMap.put("California", 55);
        this.electoralVotesMap.put("Colorado", 9);
        this.electoralVotesMap.put("Connecticut", 7);
        this.electoralVotesMap.put("Delaware", 3);
        this.electoralVotesMap.put("Florida", 29);
        this.electoralVotesMap.put("Georgia", 16);
        this.electoralVotesMap.put("Hawaii", 4);
        this.electoralVotesMap.put("Idaho", 4);
        this.electoralVotesMap.put("Illinois", 20);
        this.electoralVotesMap.put("Indiana", 11);
        this.electoralVotesMap.put("Iowa", 6);
        this.electoralVotesMap.put("Kansas", 6);
        this.electoralVotesMap.put("Kentucky", 8);
        this.electoralVotesMap.put("Louisiana", 8);
        this.electoralVotesMap.put("Maine", 4);
        this.electoralVotesMap.put("Maryland", 10);
        this.electoralVotesMap.put("Massachusetts", 11);
        this.electoralVotesMap.put("Michigan", 16);
        this.electoralVotesMap.put("Minnesota", 10);
        this.electoralVotesMap.put("Mississippi", 6);
        this.electoralVotesMap.put("Missouri", 10);
        this.electoralVotesMap.put("Montana", 3);
        this.electoralVotesMap.put("Nebraska", 5);
        this.electoralVotesMap.put("Nevada", 6);
        this.electoralVotesMap.put("New Hampshire", 4);
        this.electoralVotesMap.put("New Jersey", 14);
        this.electoralVotesMap.put("New Mexico", 5);
        this.electoralVotesMap.put("New York", 29);
        this.electoralVotesMap.put("North Carolina", 15);
        this.electoralVotesMap.put("North Dakota", 3);
        this.electoralVotesMap.put("Ohio", 18);
        this.electoralVotesMap.put("Oklahoma", 7);
        this.electoralVotesMap.put("Oregon", 7);
        this.electoralVotesMap.put("Pennsylvania", 20);
        this.electoralVotesMap.put("Rhode Island", 4);
        this.electoralVotesMap.put("South Carolina", 9);
        this.electoralVotesMap.put("South Dakota", 3);
        this.electoralVotesMap.put("Tennessee", 11);
        this.electoralVotesMap.put("Texas", 38);
        this.electoralVotesMap.put("Utah", 6);
        this.electoralVotesMap.put("Vermont", 3);
        this.electoralVotesMap.put("Virginia", 13);
        this.electoralVotesMap.put("Washington", 12);
        this.electoralVotesMap.put("West Virginia", 5);
        this.electoralVotesMap.put("Wisconsin", 10);
        this.electoralVotesMap.put("Wyoming", 3);
        this.electoralVotesMap.put("Washington D.C", 3);
    }

    /**
     * Generates the list of US states
     */
    private void InitializeStatesList()
    {
        this.states = new ArrayList<String>();

        for (String state : this.electoralVotesMap.keySet())
        {
            this.states.add(state);
        }
    }

    /**
     * Prints out the solutions onto console
     * @param solutions
     */
    /*
    private void PrintSolutions(List<List<String>> solutions)
    {
        if (solutions == null)
        {
            System.out.println("Solutions size: 0");
            return;
        }

        System.out.println("Solutions size: " + solutions.size());

        for (List<String> solution : solutions)
        {
            int sum = 0;
            for (String state : solution)
            {
                int number = this.electoralVotesMap.get(state);
                sum += number;
                System.out.print(state + "(" + number + ")  ");
            }

            System.out.print(" = " + sum);
            System.out.println();
        }
    }
    */
}
